#include <iostream>
#include <fstream>
#include <vector>
#include <functional>
#include <algorithm>
#include <ctime>
#include <queue>
#include <stack>


using namespace std;
template <typename Comparable>
class AVLTree
{
private:
	//定义BinaryNode
	struct AVLNode
	{
		Comparable element;
		AVLNode *left;
		AVLNode *right;
		int height;
		
		AVLNode(const Comparable & theElement, AVLNode *lt, AVLNode *rt, int h = 0) :element{ theElement }, left{ lt }, right{ rt }, height{ h }{ }

		AVLNode(Comparable && theElement, AVLNode *lt, AVLNode *rt,int h = 0) :element{ std::move(theElement) }, left{ lt }, right{ rt }, height{ h }{ }

	};

	AVLNode *root;
private:
	//将全部函数复制于此处。

	static const int ALLOWED_IMBALANCE = 1;

	void rotateWithRightChild(AVLNode * & k2)
	{
		AVLNode *k1 = k2->right;
		k2->right = k1->left;
		k1->left = k2;

		k2->height = max(height(k2->left), height(k2->right)) + 1;
		k1->height = max(height(k1->right), k2->height) + 1;
		k2 = k1;
	}
	void rotateWithLeftChild(AVLNode * & k2)
	{
		AVLNode *k1 = k2->left;
		k2->left = k1->right;
		k1->right = k2;
		k2->height = max(height(k2->left), height(k2->right)) + 1;
		k1->height = max(height(k1->left), k2->height) + 1;
		k2 = k1;
	}

	void doubleWithLeftChild(AVLNode * & k3)
	{
		rotateWithRightChild(k3->left);
		rotateWithLeftChild(k3);

	}
	void doubleWithRightChild(AVLNode * & k3)
	{
		rotateWithLeftChild(k3->right);
		rotateWithRightChild(k3);

	}

	void balance(AVLNode * & t)
	{
		if (t == nullptr)
			return;
		if (height(t->left) - height(t->right) > ALLOWED_IMBALANCE)
			if (height(t->left->left) >= height(t->left->right))
				rotateWithLeftChild(t);
			else
				doubleWithLeftChild(t);
		else
			if (height(t->right) - height(t->left) > ALLOWED_IMBALANCE)
				if (height(t->right->right) >= height(t->right->left))
					rotateWithRightChild(t);
				else
					doubleWithRightChild(t);

		t->height = max(height(t->left), height(t->right)) + 1;

	}
	
	void insert(const Comparable & x, AVLNode * & t)
	{
		if (t == nullptr)
			t = new AVLNode(x, nullptr, nullptr);
		else if (x < t->element)
			insert(x, t->left);
		else if (t->element < x)
			insert(x, t->right);
		
		balance(t);
	};

	
	void insert(Comparable && x, AVLNode * & t)
	{
		if (t == nullptr)
			t = new AVLNode{ std::move(x),nullptr,nullptr };
		else if (x < t->element)
			insert(std::move(x), t->left);
		else if (t->element < x)
			insert(std::move(x), t->right);
		
		balance(t);

	};
	void remove(const Comparable & x, AVLNode * & t)
	{
		if (t == nullptr)
			return;
		if (x < t->element)
			remove(x, t->left);
		else if (t->element < x)
			remove(x, t->right);
		else if (t->left != nullptr && t->right != nullptr)
		{
			t->element = findMin(t->right)->element;
			remove(t->element, t->right);
		}
		else
		{
			AVLNode * oldNode = t;
			t = (t->left != nullptr) ? t->left : t->right;
			delete oldNode;
		}
		balance(t);
	};

	AVLNode * findMax(AVLNode *t) const //递归型
	{
		if (t == nullptr)
			return nullptr;
		if (t->right == nullptr)
			return t;
		return findMax(t->right);
	};
	AVLNode * findMin(AVLNode *t) const //递归型
	{
		if (t == nullptr)
			return nullptr;
		if (t->left == nullptr)
			return t;
		return findMin(t->left);
	};

	bool contains(const Comparable & x, AVLNode *t) const
	{
		if (t == nullptr)
			return false;
		else if (x < t->element)
			return contains(x, t->left);
		else if (t->element < x)
			return contains(x, t->right);
		else
			return true;
	};
	void makeEmpty(AVLNode * & t)
	{
		if (t != nullptr)
		{
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		t = nullptr;
	};
	void printTree(AVLNode *t, ostream & out)const
	{
		if (t != nullptr)
		{
			printTree(t->left, out);
			out << t->element << endl;
			printTree(t->right, out);
		}
	};

	//clone 
	AVLNode * clone(AVLNode *t)const
	{
		if (t == nullptr)
			return nullptr;
		else
			return new AVLNode{ t->element,clone(t->left),clone(t->right) };
	};
	//中序遍历并覆盖vector，为HOMEWORK ONE 和HOMEWORK TWO做准备。
	vector<Comparable> cover(AVLNode *t, vector<Comparable> data)const
	{
		if (t == nullptr)
		{
			return data;
		}
		data = cover(t->left, data);
		data.push_back(t->element);
		data = cover(t->right, data);
		return data;

	};
	//对vector中元素乱序排列，为HOMEWORK2做准备。
	vector<Comparable> random(vector<Comparable> data)
	{
		srand((unsigned int)time(0));
		random_shuffle(data.begin(), data.end());
		return data;
	};
	void displaytree(AVLNode *t) const
	{
		queue<AVLNode*> nodes_tree;
		if (t == nullptr)
		{
			std::cout << "Empty tree." << endl;
			return;
		}
		nodes_tree.push(t);
		while (!nodes_tree.empty())
		{
			AVLNode* tmp = nodes_tree.front();
			if (tmp != nullptr)
			{
				cout << tmp->element << ",";
				nodes_tree.push(tmp->left);
				nodes_tree.push(tmp->right);
			}
			else
				cout << "-1,";
			nodes_tree.pop();

		}
		cout << "\b\b" << endl;
	}

public:
	void displaytree() const
	{
		if (isEmpty())
			cout << "Empty tree" << endl;
		else
			displaytree(root);
	}
	int height(AVLNode *t) const
	{
		return t == nullptr ? -1 : t->height;
	}
	///构造函数。
	AVLTree() //这里貌似有点问题！
	{
		//BinaryNode(NULL, nullptr, nullptr);
		root = nullptr;
	};
	/*BinarySearchTree(Comparable d)//构造时没有把d包含进树里。有点问题！
	{
		BinaryNode(d, nullptr, nullptr);
	};*/
	AVLTree(const AVLTree & rhs) : root{ nullptr }
	{
		root = clone(rhs.root);
	};
	AVLTree(AVLTree && rhs) : root{ nullptr }
	{
		root = clone(rhs.root);
	};

	~AVLTree()
	{
		makeEmpty();
	};

	///
	//find the minimum.
	const Comparable & findMin() const
	{
		return findMin(root)->element;
	};

	//find the maximum.
	const Comparable & findMax()const
	{
		return findMax(root)->element;
	};

	//确定是否包含x值。
	bool contains(const Comparable & x) const
	{
		return contains(x, root);
	};
	//判断是否为空。
	bool isEmpty() const
	{
		if (root != nullptr)
			return false;
		else
			return true;
	};
	//输出。
	void printTree(ostream & out = cout) const
	{
		if (isEmpty())
			out << "Empty tree" << endl;
		else
			printTree(root, out);
	};

	///
	//创建空树。
	void makeEmpty()
	{
		makeEmpty(root);
	};
	//插入x值。
	void insert(const Comparable & x)
	{
		insert(x, root);
	};
	//插入x值。
	void insert(Comparable && x)
	{
		insert(x, root);
	};
	//移除x值。
	void remove(const Comparable & x)
	{
		remove(x, root);
	};


	///
	//定义赋值运算符const。
	AVLTree & operator =(const AVLTree & rhs) {};
	//定义赋值运算符。
	AVLTree & operator =(AVLTree && rhs) {};

	///HOMEWORK ONE.
	//对_data中全部元素，从空树开始依次做BST插入，形成二叉搜索树，覆盖在_data中
	vector<Comparable> BST_sort(std::vector<Comparable> &_data)
	{
		int n = _data.size();
		//将data里的数据插入tree.
		for (int i = 0; i < n; i++)
		{
			insert(_data[i]);
		};
		//令tree中的数据覆盖_data.
		_data.clear();
		_data = cover(root, _data);
		//return the final _data.
		return _data;


	};
	///HOMWORK TWO.
	//对 _data 中全部元素, 先进行乱序操作, 然后从空树开始, 依次做 BST 插入, 形成二叉搜索树, 然后中序遍历输出, 覆盖在 _data 中.实现时鼓励采用相关 STL 功能
	vector<Comparable> Randomized_BST_sort(std::vector<Comparable> &_data)
	{
		//对_data中元素乱序排列。
		_data = random(_data);
		//输出乱序后的vector.
		cout << "乱序后的vector是:  ";
		for (int i = 0; i < _data.size(); i++)
		{
			cout << _data[i] << "     ";
		}
		cout << endl;
		//对乱序后的vector操作
		_data = BST_sort(_data);
		return _data;
	};

}; 




template <typename Comparable>
class splayTree
{
private:
	//定义splayNode
	struct splayNode
	{
		Comparable element;
		splayNode *left;
		splayNode *right;
		splayNode *parent;
		int height;

		splayNode(const Comparable & theElement, splayNode *lt, splayNode *rt, int h = 0) :element{ theElement }, left{ lt }, right{ rt }, height{ h }{ }

		splayNode(Comparable && theElement, splayNode *lt, splayNode *rt, int h = 0) :element{ std::move(theElement) }, left{ lt }, right{ rt }, height{ h }{ }

	};

	splayNode *root;
private:
	//在内部定义函数。
	void parent(splayNode * & t, splayNode * & node)
	{
		if (t == root)
			t->parent = nullptr;
		else if (t == nullptr)
			t->parent = nullptr;
		else if (node->left == t)
			t->parent = node;
		else if (node->right == t)
			t->parent = node;
		else
		{
			if (node->left != nullptr)
				parent(t, node->left);
			if (node->right != nullptr)
				parent(t, node->right);


		}
	}

	void insert(const Comparable & x, splayNode * & t)
	{
		if (t == nullptr)
			t = new splayNode(x, nullptr, nullptr);
		else if (x < t->element)
			insert(x, t->left);
		else if (t->element < x)
			insert(x, t->right);

		parent(t, root);
	};


	void insert(Comparable && x, splayNode * & t)
	{
		if (t == nullptr)
			t = new splayNode{ std::move(x),nullptr,nullptr };
		else if (x < t->element)
			insert(std::move(x), t->left);
		else if (t->element < x)
			insert(std::move(x), t->right);

		parent(t, root);

	};
	void remove(const Comparable & x, splayNode * & t)
	{
		if (t == nullptr)
			return;
		if (x < t->element)
			remove(x, t->left);
		else if (t->element < x)
			remove(x, t->right);
		else if (t->left != nullptr && t->right != nullptr)
		{
			t->element = findMin(t->right)->element;
			remove(t->element, t->right);
		}
		else
		{
			splayNode * oldNode = t;
			t = (t->left != nullptr) ? t->left : t->right;
			delete oldNode;
		}
	};

	splayNode * findMax(splayNode *t)  //递归型
	{
		if (t == nullptr)
			return nullptr;
		if (t->right == nullptr)
			return t;
		return findMax(t->right);
	};
	splayNode * findMin(splayNode *t)//递归型
	{
		if (t == nullptr)
			return nullptr;
		if (t->left == nullptr)
			return t;
		return findMin(t->left);
	};







	////////
	void change(splayNode * & t)
	{
		splayNode *parent;
		splayNode *grandparent;
		parent = t->parent;
		grandparent = parent->parent;
		int i = grandparent->left == parent ? -1 : 1;
		int j = parent->left == t ? -1 : 1;
		if (i == -1 && j == -1)
			rightdoublerotate(t);
		else if (i == -1 && j == 1)
			lrrotate(t);
		else if (i == 1 && j == -1)
			rlrotate(t);
		else
			leftdoublerotate(t);

	}
	void singleleftrotate(splayNode * & k2)
	{
		splayNode *k1 = k2->right;
		k2->right = k1->left;
		if (k2->right != nullptr)
			k2->right->parent = k2;
		k1->left = k2;
		if (k1->left != nullptr)
			k1->left->parent = k1;
		k2->height = max(height(k2->left), height(k2->right)) + 1;
		k1->height = max(height(k1->right), k2->height) + 1;
		splayNode *p = k2->parent;
		k2 = k1;
		k2->parent = p;
	}
	void singlerightrotate(splayNode * & k2)
	{
		splayNode *k1 = k2->left;
		k2->left = k1->right;
		if (k2->left != nullptr)
			k2->left->parent = k2;
		k1->right = k2;
		k1->right->parent = k1;
		k2->height = max(height(k2->left), height(k2->right)) + 1;
		k1->height = max(height(k1->left), k2->height) + 1;
		splayNode *p = k2->parent;
		k2 = k1;
		k2->parent = p;
	}
	void lrrotate(splayNode * & t)
	{
		splayNode *k = t->parent;
		singleleftrotate(k);
		singlerightrotate(k->parent);
	}
	void rlrotate(splayNode * & t)
	{
		splayNode *k = t->parent;
		singlerightrotate(k);
		singleleftrotate(k->parent);
	}
	void rightdoublerotate(splayNode * & t)
	{
		splayNode *k = t->parent;
		singlerightrotate(k);
		singlerightrotate(k->parent);
	}
	void leftdoublerotate(splayNode * & t)
	{
		splayNode *k = t->parent;
		singleleftrotate(k);
		singleleftrotate(k->parent);
	}
	void splay(splayNode * & t)
	{
		if (t != root->left && t != root->right  && t != root)
		{
			change(t);
		}
		else if (root->left == t)
			singlerightrotate(root);
		else if (root->right == t)
			singleleftrotate(root);
	}
	bool contains(const Comparable & x, splayNode * & t)
	{
		if (t == nullptr)
			return false;
		else if (x < t->element)
			return contains(x, t->left);
		else if (t->element < x)
			return contains(x, t->right);
		else
			splay(t);
		return true;
	};
	void makeEmpty(splayNode * & t)
	{
		if (t != nullptr)
		{
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		t = nullptr;
	};
	void printTree(splayNode *t, ostream & out)const
	{
		if (t != nullptr)
		{
			printTree(t->left, out);
			out << t->element << endl;
			printTree(t->right, out);
		}
	};

	//clone 
	splayNode * clone(splayNode *t)const
	{
		if (t == nullptr)
			return nullptr;
		else
			return new splayNode{ t->element,clone(t->left),clone(t->right) };
	};
	//中序遍历并覆盖vector，为HOMEWORK ONE 和HOMEWORK TWO做准备。
	vector<Comparable> cover(splayNode *t, vector<Comparable> data)const
	{
		if (t == nullptr)
		{
			return data;
		}
		data = cover(t->left, data);
		data.push_back(t->element);
		data = cover(t->right, data);
		return data;

	};
	//对vector中元素乱序排列，为HOMEWORK2做准备。
	vector<Comparable> random(vector<Comparable> data)
	{
		srand((unsigned int)time(0));
		random_shuffle(data.begin(), data.end());
		return data;
	};
	void displaytree(splayNode *t) const
	{
		queue<splayNode*> nodes_tree;
		if (t == nullptr)
		{
			cout << "Empty tree." << endl;
			return;
		}
		nodes_tree.push(t);
		while (!nodes_tree.empty())
		{
			splayNode* tmp = nodes_tree.front();
			if (tmp != nullptr)
			{
				cout << tmp->element << ",";
				nodes_tree.push(tmp->left);
				nodes_tree.push(tmp->right);
			}
			else
				cout << "-1,";
			nodes_tree.pop();

		}
		cout << "\b\b" << endl;
	}
public:
	void displaytree() const
	{
		if (isEmpty())
			cout << "Empty tree" << endl;
		else
			displaytree(root);
	}

	int height(splayNode *t) const
	{
		return t == nullptr ? -1 : t->height;
	}
	///构造函数。
	splayTree() //这里貌似有点问题！
	{
		//BinaryNode(NULL, nullptr, nullptr);
		root = nullptr;
	};
	/*BinarySearchTree(Comparable d)//构造时没有把d包含进树里。有点问题！
	{
		BinaryNode(d, nullptr, nullptr);
	};*/
	splayTree(const splayTree & rhs) : root{ nullptr }
	{
		root = clone(rhs.root);
	};
	splayTree(splayTree && rhs) : root{ nullptr }
	{
		root = clone(rhs.root);
	};

	~splayTree()
	{
		makeEmpty();
	};

	///
	//find the minimum.
	const Comparable & findMin()
	{
		return findMin(root)->element;
	};

	//find the maximum.
	const Comparable & findMax()
	{
		return findMax(root)->element;
	};

	//确定是否包含x值。
	bool contains(const Comparable & x)
	{
		return contains(x, root);
	};
	//判断是否为空。
	bool isEmpty() const
	{
		if (root != nullptr)
			return false;
		else
			return true;
	};
	//输出。
	void printTree(ostream & out = cout) const
	{
		if (isEmpty())
			out << "Empty tree" << endl;
		else
			printTree(root, out);
	};

	///
	//创建空树。
	void makeEmpty()
	{
		makeEmpty(root);
	};
	//插入x值。
	void insert(const Comparable & x)
	{
		insert(x, root);
	};
	//插入x值。
	void insert(Comparable && x)
	{
		insert(x, root);
	};
	//移除x值。
	void remove(const Comparable & x)
	{
		remove(x, root);
	};



	///
	//定义赋值运算符const。
	splayTree & operator =(const splayTree & rhs) {};
	//定义赋值运算符。
	splayTree & operator =(splayTree && rhs) {};

	///HOMEWORK ONE.
	//对_data中全部元素，从空树开始依次做BST插入，形成二叉搜索树，覆盖在_data中
	vector<Comparable> BST_sort(std::vector<Comparable> &_data)
	{
		int n = _data.size();
		//将data里的数据插入tree.
		for (int i = 0; i < n; i++)
		{
			insert(_data[i]);
		};
		//令tree中的数据覆盖_data.
		_data.clear();
		_data = cover(root, _data);
		//return the final _data.
		return _data;


	};
	///HOMWORK TWO.
	//对 _data 中全部元素, 先进行乱序操作, 然后从空树开始, 依次做 BST 插入, 形成二叉搜索树, 然后中序遍历输出, 覆盖在 _data 中.实现时鼓励采用相关 STL 功能
	vector<Comparable> Randomized_BST_sort(std::vector<Comparable> &_data)
	{
		//对_data中元素乱序排列。
		_data = random(_data);
		//输出乱序后的vector.
		cout << "乱序后的vector是:  ";
		for (int i = 0; i < _data.size(); i++)
		{
			cout << _data[i] << "     ";
		}
		cout << endl;
		//对乱序后的vector操作
		_data = BST_sort(_data);
		return _data;
	};

};
